from typing import *


class Solution:

    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)
        f = [0] * n
        s = []
        for i in range(n - 1):
            heights = maxHeights[i]
            while len(s) > 0 and heights <= maxHeights[s[-1]]:
                s.pop(-1)
            idx = s[-1] + 1 if len(s) > 0 else 0
            c = heights * (i - idx + 1)
            f[i + 1] = c + f[idx]
            s.append(i)
        s = []
        p = [0] * n
        ans = 0
        for i in range(n - 1, -1, -1):
            heights = maxHeights[i]
            while len(s) > 0 and heights <= maxHeights[s[-1]]:
                s.pop(-1)
            idx = s[-1] if len(s) > 0 else n
            c = heights * (idx - i)
            p[i] = c if  idx == n else c + p[idx]
            ans = max(ans,p[i] + f[i])
            s.append(i)
        return ans


so = Solution()
case = [[5, 3, 4, 1, 1]]
for c in case:
    print(so.maximumSumOfHeights(c))